{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6e92f71a",
   "metadata": {},
   "source": [
    "# 玻色采样(Boson Sampling)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eaa742ca",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-06-14T09:33:06.324239Z",
     "start_time": "2024-06-14T09:33:06.311837Z"
    }
   },
   "source": [
    "玻色采样由Aaronson和Arkhipov引入[1]，它描述了这样一个物理过程：多个全同的单光子通过线性光学器件组成的多模光量子线路相互干涉后， \n",
    "通过多次采样可以得到输出端口对应的概率分布，如下图所示。\n",
    "\n",
    "<div style=\"margin-right: 15px; border-radius: 10px; background-color: rgb(255， 255， 255); text-align: center;\">\n",
    "    <img src=\"./fig/bs.png\" width=\"30%\"/>\n",
    "    <p style=\"padding: 10px; font-size: small; text-align: center; line-height: 0%;\">\n",
    "        <b>\n",
    "    </p>\n",
    "</div>\n",
    "\n",
    "同时玻色采样的概率分布可以由理论计算得到，数学上对应着积和式(permanent)的计算。\n",
    "\n",
    "一个 $n \\times n$ 矩阵 $A$ 的积和式的定义如下，\n",
    "\n",
    "$$\n",
    "\\mathrm{Perm}(A) = \\sum_{\\sigma\\in S_n}\\prod_{i=1}^n a_{i,\\sigma_i}\n",
    "$$\n",
    "\n",
    "其中 $S_n$ 为 $n$ 阶置换群，即包含所有 $n$ 元排列的集合，$n=2$ 时\n",
    "\n",
    "$$\n",
    "A= \\begin{pmatrix}\n",
    "a_{11}&a_{12}\\\\\n",
    "a_{21}&a_{22}\n",
    "\\end{pmatrix},\n",
    " \\ \\ \\ Perm(A) = a_{11}a_{22}+a_{12}a_{21}\n",
    "$$\n",
    "\n",
    "对玻色采样的精确模拟需要精确地求解积和式这一 $\\#P$ 难的问题。而即便在近似条件下模拟玻色采样，Aaronson 等人同样证明了其困难性。\n",
    "\n",
    "假设输入的量子态为 $N$ 模的Fock态 $|\\psi\\rangle$，$|\\psi\\rangle = |m_1, m_2,...,m_N\\rangle$, $U$ 表示光量子线路对应的酉矩阵, 对应的生成算符变换如下:\n",
    "\n",
    "$$(\\hat{a}^+_{out})_k = \\sum_{i=0}^NU_{kj}(\\hat{a}^+_{in})_j$$\n",
    "\n",
    "探测到特定的量子态组合 $|n_1,n_2,...,n_N\\rangle$ 的概率为\n",
    "\n",
    "$$\n",
    "|\\langle n_1,n_2,...,n_N|W|\\psi \\rangle|^2\n",
    "$$\n",
    "\n",
    "这里 $W$ 表示 $U$ 对量子态的作用，因为在光量子线路中的酉矩阵 $U$ 直接作用对象是生成算符和湮灭算符，所以需要 $W$ 表示对量子态的作用，具体的，\n",
    "输出的振幅可以表示成\n",
    "\n",
    "$$\n",
    "\\langle n_1,n_2,...,n_N|W|\\psi\\rangle = \\frac{Per(U_{st})}{\\sqrt{m_1!...m_N!n_1...n_N!}}\n",
    "$$\n",
    "\n",
    "输出的概率可以写成\n",
    "\n",
    "$$\n",
    "|\\langle n_1,n_2,...,n_N|W|\\psi\\rangle|^2 = \\frac{|Per(U_{st})|^2}{m_1!...m_N!n_1...n_N!}\n",
    "$$\n",
    "\n",
    "这里的 $U_{st}$ 是通过对 $U$ 取行取列组合来得到，具体来说，根据输入 $|\\psi\\rangle = |m_1, m_2,...,m_N\\rangle$ 取对应的第 $i$ 行并且重复$m_i$ 次，如果 $m_i=0$ 则不取，根据输出 $|n_1,n_2,...,n_N\\rangle$ 取对应的第 $j$ 列并且重复 $m_j$ 次，如果 $m_j=0$ 则不取。 \n",
    "\n",
    "比如下面的2光子玻色采样例子[2]\n",
    "\n",
    "<div style=\"margin-right: 15px; border-radius: 10px; background-color: rgb(255， 255， 255); text-align: center;\">\n",
    "    <img src=\"./fig/f3.png\" width=\"30%\"/>\n",
    "    <p style=\"padding: 10px; font-size: small; text-align: center; line-height: 0%;\">\n",
    "        <b>\n",
    "    </p>\n",
    "</div>\n",
    "\n",
    "假设两个光子从1、2端口输入，那么从2、3端口输出的的概率 $P_{2,3}$ 如下，\n",
    "\n",
    "$$\n",
    "P_{2,3} = U_{1,2}U_{2,3} + U_{1,3}U_{2,2} =\\mathrm{Perm}(U_{sub}) = \\mathrm{Perm}\\begin{pmatrix}U_{1,2} & U_{2,2}\\\\\n",
    "U_{1,3} & U_{2,3}\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "$U_{sub}$ 是对应的酉矩阵 $U$ 取第1、2行和第2、3列构成的子矩阵的转置。\n",
    "\n",
    "\n",
    "\n",
    "在量子模拟中，玻色采样可以用来模拟多体量子系统的动力学行为，玻色采样被用作证明量子计算机超越经典计算机能力的一种方式，即所谓的量子优越性。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72d6fa1a",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-06-17T03:00:18.435440Z",
     "start_time": "2024-06-17T03:00:17.655325Z"
    }
   },
   "source": [
    "我们以下面的4模线路为例来演示玻色采样\n",
    "<div style=\"margin-right: 15px; border-radius: 10px; background-color: rgb(255， 255， 255); text-align: center;\">\n",
    "    <img src=\"./fig/f4.png\" width=\"50%\"/>\n",
    "    <p style=\"padding: 10px; font-size: small; text-align: center; line-height: 0%;\">\n",
    "        <b>\n",
    "    </p>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8be2f71",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-06-14T09:40:26.386989Z",
     "start_time": "2024-06-14T09:40:26.383549Z"
    }
   },
   "source": [
    "# 代码示例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4c6f02a0",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-07-11T05:11:34.813669Z",
     "start_time": "2024-07-11T05:11:32.026651Z"
    }
   },
   "outputs": [],
   "source": [
    "## 构建一个由ps门和bs门组成的4模线路，设置初态为[1,1,0,0]\n",
    "import numpy as np\n",
    "import deepquantum as dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "75fbaf80",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-07-11T05:11:46.856197Z",
     "start_time": "2024-07-11T05:11:46.827294Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg baseProfile=\"full\" height=\"3.6363636363636362cm\" version=\"1.1\" width=\"12.0cm\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:ev=\"http://www.w3.org/2001/xml-events\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><defs /><polyline fill=\"none\" points=\"40,30 130,30\" stroke=\"black\" stroke-width=\"2\" /><rect fill=\"teal\" height=\"12\" rx=\"0\" ry=\"0\" stroke=\"black\" stroke-width=\"1.5\" width=\"6\" x=\"82.5\" y=\"25\" /><text font-size=\"9\" x=\"80\" y=\"20\">PS</text><text font-size=\"7\" x=\"95\" y=\"20\">θ =1.047</text><polyline fill=\"none\" points=\"40,60 130,60\" stroke=\"black\" stroke-width=\"2\" /><rect fill=\"teal\" height=\"12\" rx=\"0\" ry=\"0\" stroke=\"black\" stroke-width=\"1.5\" width=\"6\" x=\"82.5\" y=\"55\" /><text font-size=\"9\" x=\"80\" y=\"50\">PS</text><text font-size=\"7\" x=\"95\" y=\"50\">θ =1.047</text><polyline fill=\"none\" points=\"40,90 130,90\" stroke=\"black\" stroke-width=\"2\" /><rect fill=\"teal\" height=\"12\" rx=\"0\" ry=\"0\" stroke=\"black\" stroke-width=\"1.5\" width=\"6\" x=\"82.5\" y=\"85\" /><text font-size=\"9\" x=\"80\" y=\"80\">PS</text><text font-size=\"7\" x=\"95\" y=\"80\">θ =1.047</text><polyline fill=\"none\" points=\"40,120 130,120\" stroke=\"black\" stroke-width=\"2\" /><rect fill=\"teal\" height=\"12\" rx=\"0\" ry=\"0\" stroke=\"black\" stroke-width=\"1.5\" width=\"6\" x=\"82.5\" y=\"115\" /><text font-size=\"9\" x=\"80\" y=\"110\">PS</text><text font-size=\"7\" x=\"95\" y=\"110\">θ =1.047</text><polyline fill=\"none\" points=\"130,30 160,30 190,60 220,60\" stroke=\"black\" stroke-width=\"2\" /><polyline fill=\"none\" points=\"130,60 160,60 190,30 220,30\" stroke=\"black\" stroke-width=\"2\" /><text font-size=\"9\" x=\"170\" y=\"25\">BS</text><text font-size=\"7\" x=\"185\" y=\"44\">θ =0.785</text><text font-size=\"7\" x=\"185\" y=\"50\">ϕ =1.047</text><polyline fill=\"none\" points=\"130,90 160,90 190,120 220,120\" stroke=\"black\" stroke-width=\"2\" /><polyline fill=\"none\" points=\"130,120 160,120 190,90 220,90\" stroke=\"black\" stroke-width=\"2\" /><text font-size=\"9\" x=\"170\" y=\"85\">BS</text><text font-size=\"7\" x=\"185\" y=\"104\">θ =0.785</text><text font-size=\"7\" x=\"185\" y=\"110\">ϕ =1.047</text><polyline fill=\"none\" points=\"220,60 250,60 280,90 310,90\" stroke=\"black\" stroke-width=\"2\" /><polyline fill=\"none\" points=\"220,90 250,90 280,60 310,60\" stroke=\"black\" stroke-width=\"2\" /><text font-size=\"9\" x=\"260\" y=\"55\">BS</text><text font-size=\"7\" x=\"275\" y=\"74\">θ =0.785</text><text font-size=\"7\" x=\"275\" y=\"80\">ϕ =1.047</text><polyline fill=\"none\" points=\"310,30 340,30 370,60 400,60\" stroke=\"black\" stroke-width=\"2\" /><polyline fill=\"none\" points=\"310,60 340,60 370,30 400,30\" stroke=\"black\" stroke-width=\"2\" /><text font-size=\"9\" x=\"350\" y=\"25\">BS</text><text font-size=\"7\" x=\"365\" y=\"44\">θ =1.047</text><text font-size=\"7\" x=\"365\" y=\"50\">ϕ =0.785</text><polyline fill=\"none\" points=\"310,90 340,90 370,120 400,120\" stroke=\"black\" stroke-width=\"2\" /><polyline fill=\"none\" points=\"310,120 340,120 370,90 400,90\" stroke=\"black\" stroke-width=\"2\" /><text font-size=\"9\" x=\"350\" y=\"85\">BS</text><text font-size=\"7\" x=\"365\" y=\"104\">θ =1.047</text><text font-size=\"7\" x=\"365\" y=\"110\">ϕ =0.785</text><polyline fill=\"none\" points=\"220,30 310,30\" stroke=\"black\" stroke-width=\"2\" /><polyline fill=\"none\" points=\"220,120 310,120\" stroke=\"black\" stroke-width=\"2\" /><text font-size=\"12\" x=\"25\" y=\"30\">0</text><text font-size=\"12\" x=\"25\" y=\"60\">1</text><text font-size=\"12\" x=\"25\" y=\"90\">2</text><text font-size=\"12\" x=\"25\" y=\"120\">3</text></svg>"
      ],
      "text/plain": [
       "<svgwrite.drawing.Drawing at 0x28bd062ca30>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "init_state = [1,1,0,0]\n",
    "cir = dq.QumodeCircuit(nmode=4, init_state=init_state, backend='fock')\n",
    "for k in range(4):\n",
    "    cir.ps(wires=[k], inputs=np.pi/3)\n",
    "cir.bs(wires=[0,1], inputs=[np.pi/4,np.pi/3])\n",
    "cir.bs(wires=[2,3], inputs=[np.pi/4,np.pi/3])\n",
    "cir.bs(wires=[1,2], inputs=[np.pi/4,np.pi/3])\n",
    "cir.bs(wires=[0,1], inputs=[np.pi/3,np.pi/4])\n",
    "cir.bs(wires=[2,3], inputs=[np.pi/3,np.pi/4])\n",
    "#线路可视化\n",
    "cir.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "5926c114",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-07-11T05:11:48.250815Z",
     "start_time": "2024-07-11T05:11:48.170085Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "final state {|1100>: tensor([0.2652-0.5714j]), |0200>: tensor([0.3709-0.2652j]), |1001>: tensor([0.1875+0.3248j]), |0002>: tensor([0.2296+0.1326j]), |0011>: tensor([0.2091-0.0560j]), |1010>: tensor([0.2091+0.0560j]), |0101>: tensor([0.0560-0.2091j]), |2000>: tensor([-0.0884+0.1121j]), |0110>: tensor([-0.0625-0.1083j]), |0020>: tensor([0.0442-0.0765j])}\n",
      "sample results {|1100>: 404, |0110>: 15, |2000>: 17, |1001>: 150, |0200>: 218, |1010>: 58, |0002>: 67, |0011>: 49, |0101>: 40, |0020>: 6}\n"
     ]
    }
   ],
   "source": [
    "# 线路进行演化\n",
    "state = cir()\n",
    "#对演化之后的结果采样\n",
    "sample = cir.measure(shots=1024)\n",
    "print('final state',state)\n",
    "print('sample results', sample)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97a307ef",
   "metadata": {},
   "source": [
    "根据前面的讨论可以知道输出的概率是可以理论计算的，下面我们将分步计算输出的概率并验证"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "32a0bd1a",
   "metadata": {},
   "source": [
    "1. 计算光量子线路对应的酉矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d2ae416e",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-07-11T05:11:50.379280Z",
     "start_time": "2024-07-11T05:11:50.362337Z"
    }
   },
   "outputs": [],
   "source": [
    "## 计算光量子线路的酉矩阵\n",
    "u_ps = np.diag([np.exp(1j*np.pi/3), np.exp(1j*np.pi/3), np.exp(1j*np.pi/3), np.exp(1j*np.pi/3) ])\n",
    "\n",
    "u_bs1 = np.array([[np.cos(np.pi/4), -np.exp(-1j*np.pi/3)*np.sin(np.pi/4)],\n",
    "                  [np.exp(1j*np.pi/3)*np.sin(np.pi/4), np.cos(np.pi/4)]])\n",
    "u_bs1 = np.block([[u_bs1, np.zeros([2,2])],\n",
    "                 [np.zeros([2,2]), np.eye(2)]])\n",
    "\n",
    "u_bs2 = np.array([[np.cos(np.pi/4), -np.exp(-1j*np.pi/3)*np.sin(np.pi/4)],\n",
    "                  [np.exp(1j*np.pi/3)*np.sin(np.pi/4), np.cos(np.pi/4)]])\n",
    "u_bs2 = np.block([[np.eye(2), np.zeros([2,2])],\n",
    "                 [np.zeros([2,2]), u_bs2]])\n",
    "\n",
    "u_bs3 =np.array([[np.cos(np.pi/4), -np.exp(-1j*np.pi/3)*np.sin(np.pi/4)],\n",
    "                  [np.exp(1j*np.pi/3)*np.sin(np.pi/4), np.cos(np.pi/4)]])\n",
    "u_bs3 = np.block([[1, np.zeros(2), 0],\n",
    "                 [np.zeros([2,1]),u_bs3, np.zeros([2,1])],\n",
    "                 [0, np.zeros(2), 1]])\n",
    "\n",
    "u_bs4 = np.array([[np.cos(np.pi/3), -np.exp(-1j*np.pi/4)*np.sin(np.pi/3)],\n",
    "                  [np.exp(1j*np.pi/4)*np.sin(np.pi/3), np.cos(np.pi/3)]])\n",
    "u_bs4 = np.block([[u_bs4, np.zeros([2,2])],\n",
    "                 [np.zeros([2,2]), np.eye(2)]])\n",
    "\n",
    "u_bs5 = np.array([[np.cos(np.pi/3), -np.exp(-1j*np.pi/4)*np.sin(np.pi/3)],\n",
    "                  [np.exp(1j*np.pi/4)*np.sin(np.pi/3), np.cos(np.pi/3)]])\n",
    "u_bs5 = np.block([[np.eye(2), np.zeros([2,2])],\n",
    "                 [np.zeros([2,2]), u_bs5]])\n",
    "\n",
    "u_total = u_bs5 @ u_bs4 @ u_bs3 @ u_bs2 @ u_bs1 @ u_ps"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04bf5443",
   "metadata": {},
   "source": [
    "2. 计算输出结果及对应的子矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "00264f2d",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-07-11T05:11:52.418391Z",
     "start_time": "2024-07-11T05:11:52.409422Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.06470476-0.11207193j -0.77181154-0.11207193j]\n",
      " [-0.28349365+0.8080127j  -0.3080127 -0.21650635j]]\n"
     ]
    }
   ],
   "source": [
    "out_state = [1,1,0,0]\n",
    "u_sub = u_total[:2][:,:2]\n",
    "print(u_sub)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0511f60f",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-06-17T05:41:18.505311Z",
     "start_time": "2024-06-17T05:41:18.497575Z"
    }
   },
   "source": [
    "3. 计算子矩阵对应的permanent可以得到对应概率"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "81cf3d86",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-07-11T05:11:53.509886Z",
     "start_time": "2024-07-11T05:11:53.496932Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0.2651650429449553-0.5713512607928528j) tensor([0.2652-0.5714j])\n"
     ]
    }
   ],
   "source": [
    "per = u_sub[0,0]*u_sub[1,1] + u_sub[0,1]*u_sub[1,0]\n",
    "amp = per\n",
    "prob = abs(per)**2\n",
    "print(amp, state[dq.FockState(out_state)])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "988c669c",
   "metadata": {},
   "source": [
    "# 附录"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f87ab76d",
   "metadata": {},
   "source": [
    "[1] Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. Theory of Computing, 9(1):143–252, 2013. doi:10.4086/toc.2013.v009a004.\n",
    "\n",
    "[2] Gard, B. T., Motes, K. R., Olson, J. P., Rohde, P. P., & Dowling, J. P. (2015). An introduction to boson-sampling. In From atomic to mesoscale: The role of quantum coherence in systems of various complexities (pp. 167-192)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "dq_v3",
   "language": "python",
   "name": "dq_v3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.14"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
